package a_microsoft.year2017Autumn.problem3;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

/**
 * 维护一个包含Event的优先级队列。
 * 
 * @author I321035
 *
 */
public class Solution {
	private static Student[] students;
	private static int[] officeAvailableTime;
	private static PriorityQueue<RegistrationEvent> eventsQueue=new PriorityQueue<>(new Comparator<RegistrationEvent>(){
		@Override
		public int compare(RegistrationEvent o1, RegistrationEvent o2) {
			if(o1.begin==o2.begin)
				return Integer.compare(o1.studentId, o2.studentId);
			return Integer.compare(o1.begin, o2.begin);
		}
		
	});
	
	private static int k,m,n;
	
	public static void main(String[] args){
		Helper.generateInputStream(new String[]{"2 2 100","","1600012345 500 2 1 500 2 500","1600054321 1100 1 2 300"});
		Scanner scanner=new Scanner(System.in);
		n=scanner.nextInt();m=scanner.nextInt();k=scanner.nextInt();
		students=new Student[n];
		officeAvailableTime=new int[m+1];
		for(int i=0;i<n;i++){
			int studentId=scanner.nextInt();
			int arriveTime=scanner.nextInt();
			int offices=scanner.nextInt();
			Student stu=new Student(studentId);
			stu.arriveTime=arriveTime;
			for(int j=0;j<offices;j++){
				stu.officesToBeVisited.add(new OfficeDuration(scanner.nextInt(),scanner.nextInt()));
			}
			students[i]=stu;
		}
		run();
		for(Student s:students){
			System.out.println(s.finishTime);
		}
		scanner.close();
	}
	
	public static void run(){
		init();
		while(!eventsQueue.isEmpty()){
			RegistrationEvent event=eventsQueue.poll();
			Student stu=students[event.studentIndexInArray];
			if(officeAvailableTime[event.officeId]>event.begin){
				event.begin=officeAvailableTime[event.officeId];
			}
			int finishTime=event.begin+event.duration;
			stu.finishTime=finishTime;
			//add new Event
			OfficeDuration nextOffice=stu.officesToBeVisited.poll();
			if(nextOffice!=null){
				eventsQueue.add(new RegistrationEvent(event.studentIndexInArray,stu.studentId,nextOffice.officeId,finishTime+k,nextOffice.duration));
			}
			//set Office available time
			officeAvailableTime[event.officeId]=event.begin+event.duration;
		}
	}
	
	private static void init(){
		for(int i=0;i<students.length;i++){
			Student stu=students[i];
			OfficeDuration office=stu.officesToBeVisited.poll();
			eventsQueue.add(new RegistrationEvent(i,stu.studentId,office.officeId,stu.arriveTime+k,office.duration));
		}
	}
	
	private static class Student{
		int studentId;
		int arriveTime;
		int finishTime;
		Queue<OfficeDuration> officesToBeVisited;
		
		public Student(int id){
			studentId=id;
			officesToBeVisited=new LinkedList<>();
		}
	}
	
	private static class RegistrationEvent{
		int studentIndexInArray;
		int studentId;
		int officeId;
		int begin;
		int duration;
		
		public RegistrationEvent(int studentIndexInArray,int studentId, int officeId, int begin, int duration) {
			super();
			this.studentIndexInArray=studentIndexInArray;
			this.studentId = studentId;
			this.officeId = officeId;
			this.begin = begin;
			this.duration = duration;
		}
	}
	
	private static class OfficeDuration{
		int officeId;
		int duration;
		public OfficeDuration(int officeId, int duration) {
			super();
			this.officeId = officeId;
			this.duration = duration;
		}
	}		
}
